
// Implementation of a dictionary using an array and binary search
// It will inherit from the ArrayDictionary

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "bsearch-dictionary.h"

// Constructor
BinarySearchDictionary::BinarySearchDictionary()
{
	sorted = false;
}

bool
BinarySearchDictionary::addRecord( KeyType key, DataType record) {
	sorted = false;
	return ArrayDictionary::addRecord(key, record);
}

// Find a key in the dictionary and return corresponding record or NULL
DataType
BinarySearchDictionary::findRecord( KeyType key)
{
	if (!sorted) {
		sort();
		sorted = true;
	}

	// Use binary search

	// Add your implementation here
	return binarySearch(0, currentNumber);
}


// Sort array using heap sort
void
BinarySearchDictionary::sort()
{
	//printf("Before\n");
	//for (int i = 0; i < currentNumber; i++) {
	//	printf("%s\n", array[i].key);
	//}

	int start = currentNumber /2 - 1;

	while (start >= 0) {
		int root = start;
		while (root * 2 +1 <= currentNumber) {
			int child = root * 2 + 1;
			int swap = root;
			if (array[swap],key < array[child].key)
				swap = child;
			if (child + 1 <= end && array[swap] < array[child+1])
				swap = child+1;
			if (swap != root) {
				void *temp = array[child];
				array[child] = array[swap];
				array[swap] = temp;
			}
			else
				break;
		}
		start--;
	}

	int end = currentNumber;
	while (end > 0) {
		void *temp = array[0];
		array[0] = array[end];
		array[end] = temp;
		end--;
		root = 0;
		while (root * 2 +1 <= currentNumber) {
			int child = root * 2 + 1;
			int swap = root;
			if (array[swap],key < array[child].key)
				swap = child;
			if (child + 1 <= end && array[swap] < array[child+1])
				swap = child+1;
			if (swap != root) {
				void *temp = array[child];
				array[child] = array[swap];
				array[swap] = temp;
			}
			else
				break;
		}
	}

	//printf("After\n");
	//for (int i = 0; i < currentNumber; i++) {
	//	printf("%s\n", array[i].key);
	//}
}

DataType BinarySearchDictionary::binarySearch(int start, int end, KeyType key) {
	int mid = (end - start) / 2;
	if (!strcmp(key, array[mid].key))
		return array[mid].data;
	else if (start == end)
		return NULL;
	else if (strcmp(key, array[mid].key) > 0) {
		start = mid;
		return binarySearch(start, end, key);
	}
	else {
		end = mid;
		return binarySearch(start, end, key);
	}
}


